package xin.javashare.javacollectionsframework.mycollectionsframework;

public class MyLinkedList<E> extends MyArrayList<E> {
    private Node<E> head, tail;

    /**
     * Create a default list
     */
    public MyLinkedList() {
    }

    /**
     * Create a list from an array of objects
     */
    public MyLinkedList(E[] objects) {
        super(objects); // ?
    }

    /**
     * Return the head element in the list
     */
    public E getFirst() {
        if (size == 0) {
            return null;
        } else
            return head.element;
    }

    /**
     * Return the last element in the list
     */
    public E getLast() {
        if (size == 0) {
            return null;
        } else
            return tail.element;
    }

    /**
     * Add an element to the beginning of the list
     */
    public void addFirst(E e) {
        Node<E> newNode = new Node<E>(e);

        newNode.next = head;
        head = newNode;
        size++;

        if (tail == null)
            tail = head;
    }

    /**
     * Add an element to the end of the list
     */
    public void addLast(E e) {
        Node<E> newNode = new Node<E>(e);

        if (tail == null) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            tail = tail.next;
        }

        size++;
    }

    public void add(int index, E e) {
        if (index == 0) addFirst(e);
        else if (index >= size) addLast(e);
        else {
            Node<E> current = head;
            for (int i = 1; i < index; i++) {
                current = current.next;
            }
            Node<E> temp = current.next;

            current.next = new Node<E>(e);
            (current.next).next = temp;

            size++;
        }
    }

    public E removeFirst() {
        if (size == 0) return null;
        else {
            Node<E> temp = head;
            head = head.next; // 若只有1个结点,head = tail, tail.next = null
            // --->head = head.next = null；因此不用开始就讨论size = 1的情况？
            size--;
            if (size == 1) {
                tail.next = null;
            }
            return temp.element;
        }
    }

    public E removeLast() {
        if (size == 0) return null;
        else if (size == 1) {
            Node<E> temp = tail;
            head = tail = null;
            size = 0;
            return temp.element;
        } else {
            Node<E> current = head;
            // 从i=0开始遍历，最后指向i+1 不要从i=1开始
            for (int i = 0; i < size - 2; i++) {
                current = current.next; // size-2
            }

            Node<E> temp = tail;
            tail = current; // 新tail指向前一个结点size-2
            tail.next = null;
            size--;
            return temp.element;
        }
    }

    public E remove(int index) {
        if (index < 0 || index >= size) return null;
        else if (index == 0) return removeFirst();
        else if (index == size - 1) return removeLast();
        else {
            Node<E> current = head;
            for (int i = 1; i < index; i++) {
                current = current.next; // current指向 index前一个节点(index - 1)
            }

            Node<E> temp = current.next;
            current.next = temp.next;
            size--;
            return temp.element;
        }
    }

    public String toString() {
        StringBuilder result = new StringBuilder("[");

        Node<E> current = head;
        for (int i = 0; i < size; i++) {
            result.append(current.element);
            current = current.next;
            if (current != null) {
                result.append(", ");
            } else {
                result.append("]");
            }
        }

        return result.toString();
    }

    /**
     * Clear the list
     */
    public void clear() {
        head = tail = null;
//		size = 0;
    }

    public boolean contains(E e) {
        Node<E> current = head;
        for (int i = 0; i < size; i++) {
            if (current.element == e)
                return true;
            else
                current = current.next;
        }

        return false;
    }

    public E get(int index) {
        if (index < 0 || index >= size) return null;
        else {
            Node<E> current = head;
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
            return current.element;
        }
    }

    public int indexOf(E e) {
        Node<E> current = head;
        for (int i = 0; i < size; i++) {
            if (current.element == e) return i;
            current = current.next;
        }

        return -1;
    }

    public int lastIndexOf(E e) {
        Node<E> current = head;
        int result = -1;
        ;
        for (int i = 0; i < size; i++) {
            if (current.element == e) result = i;
            current = current.next;
        }

        return result;
    }

    public E set(int index, E e) {
        Node<E> newNode = new Node<E>(e);

        Node<E> current = head;
        for (int i = 0; i < index - 1; i++) {
            current = current.next; // index -1
        }

        Node<E> oldNode = current.next; // index
        newNode.next = current.next.next; // index + 1
        current.next = newNode; // index

        return oldNode.element;
    }

    // ?????????????????
    private static class Node<E> {
        E element;

        Node<E> next;

        public Node(E element) {
            this.element = element;
        }
    }
}
